4738. Sorting

 

Sort the array of integers in non-increasing order.

 

Input. The first line contains the size of the array n (1 ≤ n ≤ 1000). The second line contains n integers, not exceeding 2 *109 in absolute value.

 

Output. Print the given numbers in non-increasing order.

 

Sample input

Sample output

5

9 2 7 1 2

9 7 2 2 1

 

 

SOLUTION

sort

 

Algorithm analysis

To sort the integers in non-increasing order, you can use any sorting algorithm.

For example, you can use the sort function from the STL. To specify the sorting direction, you can utilize comparators:

·        less<int>() – for sorting in ascending order;

·        greater<int>() – for sorting in descending order;

These comparators are defined in the <set> library.

 

Algorithm implementation

Declare the array.

 

#define MAX 1010

int m[MAX];

 

Read the input data.

 

scanf("%d",&n);

for(i = 0; i < n; i++)

  scanf("%d",&m[i]);

 

Sort the array in descending order.

 

sort(m,m+n,greater<int>());

 

Print the resulting array.

 

for(i = 0; i < n; i++)

  printf("%d ",m[i]);

printf("\n");

 

Algorithm implementation – vector

Declare a vector to store the input sequence of numbers.

 

vector<int> v;

 

Read the input data.

 

scanf("%d",&n);

v.resize(n);

for(i = 0; i < n; i++)

  scanf("%d",&v[i]);

 

Sort the array in descending order.

 

sort(v.begin(),v.end(),greater<int>());

 

Print the resulting array.

 

for(i = 0; i < v.size(); i++)

  printf("%d ",v[i]);

printf("\n");

 

Algorithm implementation – comparator

Declare the array.

 

#define MAX 1001

int m[MAX];

 

Declare a function – comparator f to sort integers in descending order.

 

int f(int a, int b)

{

  return a > b;

}

 

The main part of the program. Read the input data.

 

scanf("%d", &n);

for (i = 0; i < n; i++)

  scanf("%d", &m[i]);

 

Sort the array in descending order using a comparator.

 

sort(m, m + n, f);

 

Print the resulting array.

 

for (i = 0; i < n; i++)

  printf("%d ", m[i]);

printf("\n");

 

Java implementation – comparator

 

import java.util.*;

 

public class Main

{

  public static class MyFun implements Comparator<Integer>

  {

    public int compare(Integer a, Integer b)

    {

      return b - a;

    }

  }

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    Integer m[] = new Integer[n];

 

    for(int i = 0; i < n; i++)

      m[i] = con.nextInt();

 

    Arrays.sort(m, new MyFun());

 

    for(int i = 0; i < n; i++)

      System.out.print(m[i] + " ");

 

    System.out.println();

 

    con.close();

  }

}

 

Java implementation – reverse order

 

import java.util.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    Integer m[] = new Integer[n];

 

    for(int i = 0; i < n; i++)

      m[i] = con.nextInt();

 

    Arrays.sort(m,Collections.reverseOrder());

 

    for(int i = 0; i < n; i++)

      System.out.print(m[i] + " ");

 

    System.out.println();

 

    con.close();

  }

}

 

Python implementation

Read the input data.

 

n = int(input())

lst = list(map(int,input().split()))

 

Sort the list in descending order.

 

lst.sort(reverse = True)

 

Print the numbers in non-increasing order.

 

print(*lst)